package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Sum3 {

    public static void main(String[] args) {
        Sum3 sum3 = new Sum3();
        List<List<Integer>> lists = sum3.threeSum(new int[]{0,0,0});
        System.out.println(lists);
    }


    public List<List<Integer>> threeSum(int[] nums) {
        if(nums.length < 3) return new ArrayList();
        List<List<Integer>> l = new ArrayList<>();
        Arrays.sort(nums);
        for (int first = 0; first < nums.length; ++first) {
            if(first > 0 && nums[first] == nums[first - 1]) continue;
            int third = nums.length - 1;
            int target = -nums[first];
            for (int second = first + 1; second < nums.length; ++second) {
                if(second > first + 1 && nums[second] == nums[second - 1]) continue;
                while(second < third && nums[second] + nums[third] > target){
                    third --;
                }
                if (second == third) {
                    break;
                }
                if(nums[second] + nums[third] == target){
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    l.add(list);
                }
            }
        }
        return l;
    }


    private void sortArr(int[] arr, int start, int end){
        if (arr.length < 1 || start < 0 || end > arr.length || start >= end) return ;
        int privot = arr[start];
        int i = start, j = end;
        while(i < j){
            while(i < j && arr[j] > privot){
                j --;
            }
            if(i < j && arr[i] > arr[j]){
                arr[i++] = arr[j];
            }
            while(i < j && arr[i] < privot){
                i ++;
            }
            if(i < j && arr[i] > arr[j]){
                arr[j--] = arr[i];
            }
        }
        arr[i] = privot;
        sortArr(arr, start, i - 1);
        sortArr(arr, i + 1, end);
    }

}
